package com.tucc.hello.leetcode.no1_400.no1_200.no81_100.no90;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.subsetsWithDup(new int[]{4, 4, 4, 1, 4}));
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i <= n; i++) {
            resultList.addAll(combine(nums, n, i));
        }
        return resultList;
    }

    public List<List<Integer>> combine(int[] nums, int n, int k) {
        List<List<Integer>> resultList = new ArrayList<>();
        combine(nums, 0, n, k, new ArrayList<>(), resultList);
        return resultList;
    }

    public void combine(int[] nums, int cur, int n, int k, List<Integer> list, List<List<Integer>> resultList) {
        if (list.size() == k) {
            resultList.add(new ArrayList<>(list));
        } else {
            for (int i = cur; i < n; i++) {
                list.add(nums[i]);
                combine(nums, i + 1, n, k, list, resultList);
                list.remove(list.size() - 1);
                while (i + 1 < n && nums[i + 1] == nums[i]) {
                    i++;
                }
            }
        }
    }
}
